//给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：
// 
//
// 
// 每次转换只能改变一个字母。 
// 转换过程中的中间单词必须是字典中的单词。 
// 
//
// 说明: 
//
// 
// 如果不存在这样的转换序列，返回 0。 
// 所有单词具有相同的长度。 
// 所有单词只由小写字母组成。 
// 字典中不存在重复的单词。 
// 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。 
// 
//
// 示例 1: 
//
// 输入:
//beginWord = "hit",
//endWord = "cog",
//wordList = ["hot","dot","dog","lot","log","cog"]
//
//输出: 5
//
//解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",
//     返回它的长度 5。
// 
//
// 示例 2: 
//
// 输入:
//beginWord = "hit"
//endWord = "cog"
//wordList = ["hot","dot","dog","lot","log"]
//
//输出: 0
//
//解释: endWord "cog" 不在字典中，所以无法进行转换。 
// Related Topics 广度优先搜索 
// 👍 426 👎 0

package leetcode.editor.cn;

import java.util.*;

//Java：单词接龙
public class P127WordLadder {

    /**
     *
     * 思路：126题的步骤1加步骤2，就是本道题的答案
     *      1. 构造图，单词作为点。遍历词典，两两比较，若能够通过一个字母直接转换的，便是图的相邻的点。
     *      2. 广度遍历，得到最短的转换序列的长度 min
     *
     * 执行用时： 530 ms , 在所有 Java 提交中击败了 36.02% 的用户 内存消耗： 41.9 MB , 在所有 Java 提交中击败了 48.67% 的用户
     *
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        private Map<String, Set<String>> graph;     // 图

        public int ladderLength(String beginWord, String endWord, List<String> wordList) {
            // 将开始单词也加入到单词表中
            if (!wordList.contains(beginWord)) {
                wordList.add(beginWord);
            }

            graph = createGraph(wordList);
            return bfs(beginWord, endWord);
        }

        /**
         * 广度优先遍历，返回最短查询到的次数，查不到的话 返回-1
         */
        private int bfs(String start, String end) {
            int level = 0;
            Set<String> visit = new HashSet<>();    // 已经访问过的
            Queue<String> deque = new ArrayDeque<>();
            deque.add(start);
            visit.add(start);
            while (!deque.isEmpty()) {
                int size = deque.size();
                for (int i = 0; i < size; i++) {
                    String str = deque.poll();
                    if (end.equals(str)) {
                        return level + 1;
                    }
                    if (graph.get(str) == null) {
                        return 0;
                    }

                    for (String word : graph.get(str)) {
                        if (visit.contains(word)) {
                            continue;
                        }
                        visit.add(word);
                        deque.add(word);
                    }
                }
                level++;
            }
            return 0;
        }

        // 建图
        private Map<String, Set<String>> createGraph(List<String> wordList) {
            Map<String, Set<String>> map = new HashMap<>();
            for (int i = 0; i < wordList.size(); i++) {
                String a = wordList.get(i);
                for (int k = i + 1; k < wordList.size(); k++) {
                    String b = wordList.get(k);
                    if (isNeighbor(a, b)) {
                        if (map.get(a) == null) {
                            map.put(a, new HashSet<>());
                        }
                        if (map.get(b) == null) {
                            map.put(b, new HashSet<>());
                        }
                        map.get(a).add(b);
                        map.get(b).add(a);
                    }
                }
            }
            return map;
        }

        // 是否邻居[可以通过一个字母直接转换]
        private boolean isNeighbor(String a, String b) {
            int diff = 0;
            for (int i = 0; i < a.length() && diff <= 1; i++) {
                if (a.charAt(i) != b.charAt(i)) {
                    diff++;
                }
            }
            return diff == 1;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        String s1 = "hit";
        String s2 = "cog";
        String[] nums = new String[]{
                "hot","dot","dog","lot","log","hit"
        };
        List<String> words = Arrays.asList(nums);
        Solution solution = new P127WordLadder().new Solution();
        System.out.println(solution.ladderLength(s1, s2, words));
        // TO TEST
    }

}